package lyl.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Inorder {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left,TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    //递归
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        List<Integer> left = inorderTraversal(root.left);
        List<Integer> right = inorderTraversal(root.right);

        result.addAll(left);
        result.add(root.val);
        result.addAll(right);
        return result;

    }

    //用栈存储节点，先进后出 先找到左边入栈，有右边就加右边
    public List<Integer> inorderTraversal2(TreeNode root){
        List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (!stack.isEmpty() || current !=null){
            //找到最左端
            while (current != null){
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            //加入左边的 如果没有右边，就出栈里的上一个加入的，是它的根节点，放入，再用它的根节点去取右节点
            result.add(current.val);
            current = current.right;
        }
        return result;

    }
}
